package com.xy6.algo.force;


/**
 * 蛮力法求解凸包问题
 * 
 * <pre>
 * 什么是凸包？ 
 * 假设平面上有p0~p12共13个点，过某些点作一个多边形，使这个多边形能把所有点都“包”起来。
 * 当这个多边形是凸多边形的时候，我们就叫它“凸包”
 * 
 * 什么是凸包问题？ 
 * 我们把这些点放在二维坐标系里面，那么每个点都能用 (x,y) 来表示。 
 * 现给出点的数目13，和各个点的坐标。求构成凸包的点
 * 
 * 对于一个n个点集合中的两个点Pi和Pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时，
 * 他们的连线是该集合凸包边界的一部分。
 * 当坐标平面上的两个点（X1,Y1）、（X2,Y2）组成的直线方程是：ax+by=c（其中a=Y2-Y1，b=X1-X2，c=X1Y2-X2Y1）
 * 这条直线将坐标平面分成分成两个半平面，其中一个平面的点都满足ax+by>c，另一个半平面的点都满足ax+by<c，
 * 在直线上的点都满足ax+by=c。
 * 因此，可以通过将点带入ax+by-c这个解析式中判断解析式值正负的方法来判断某些点是否位于这条直线的同一边。
 * 
 * 时间复杂度：O(n^3)
 * 暂未实现将凸包点按顺时针或逆时针顺序输出
 * </pre>
 * 
 * @author zhang
 * @since 2017-12-25
 */
public class ConvexHull {

	public static void main(String[] args) {
		int x[] = new int[] { 0, 2, 2, 0 };
		int y[] = new int[] { 0, 0, 2, 2 };
		ConvexHull.calc(x, y);
	}

	/**
	 * 计算构成凸包的点
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	public static int[] calc(int x[], int y[]) {
		int n = x.length;
		// 第一个有效值
		int firstVal = 0;
		// 凸包集合
		int point[] = new int[n];
		// 标记余下n-2个点是否在同一侧
		boolean bAllSame = true;
		int farPoint = -1;
		int deletePoint = -1;

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				firstVal = Integer.MAX_VALUE;
				bAllSame = true;
				farPoint = -1;
				for (int k = j + 1; k < n; k++) {
					int temp = calc(x[i], y[i], x[j], y[j], x[k], y[k]);
					// 当前点在直线上。判断是否将点加入凸包集合
					if (temp == 0) {
						double len = calc(x[i], x[j], y[i], y[j]);
						double len1 = calc(x[i], x[k], y[i], y[k]);
						double len2 = calc(x[j], x[k], y[j], y[k]);
						if(len1 <= len && len2 <= len){
						} else if(len1 < len2) {
							farPoint = k;
							deletePoint = i;
						} else if(len1 > len2){
							farPoint = k;
							deletePoint = j;
						}
						continue;
					}
					if (firstVal == Integer.MAX_VALUE) {
						// 第一个有效值
						firstVal = temp;
						continue;
					}
					if (firstVal != temp) {
						bAllSame = false;
						break;
					}
				}
				if (bAllSame) {
					if(farPoint == -1){
						// 其他点不在直线上
						point[i] = 1;
						point[j] = 1;
					} else {
						// 有点在直线上
						point[farPoint] = 1;
						if(i == deletePoint){
							point[i] = 0;
							point[j] = 1;
						} else {
							point[i] = 1;
							point[j] = 0;
						}
					}
				}
			}
		}
		
		for (int i = 0; i < x.length; i++) {
			if(point[i] == 1){
				System.out.println(String.format("%d,%d", x[i], y[i]));
			}
		}
		
		return point;
	}

	/**
	 * 根据两点确认一条直线，得到一次项表达式，将第三个点代入表达式得到结果，返回结果的符号
	 * <pre>
	 * 1，点在直线上方
	 * 0，点在直线上
	 * -1，点在直线下方
	 * </pre>
	 * 
	 * @param x1
	 * @param y1
	 * @param x2
	 * @param y2
	 * @param x3
	 * @param y3
	 * @return
	 */
	private static int calc(int x1, int y1, int x2, int y2, int x3, int y3) {
		if (x1 == x2) {
			return Integer.signum(x3 - x1);
		}
		return Integer.signum((y1 - y2) * x3 - (x1 - x2) * y3 + (x1 * y2 - x2 * y1));
	}
	
	/**
	 * 计算两点之间距离的平方
	 * 
	 * @param x1
	 * @param y1
	 * @param x2
	 * @param y2
	 * @return
	 */
	private static double calc(int x1, int x2, int y1, int y2){
		return Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2);
	}
}
